package net.cloudsun.tree.rb;

import net.cloudsun.tree.orderbinary.OrderBinaryNode;
import net.cloudsun.tree.orderbinary.OrderBinaryTree;

/**
 * 红黑树
 * @author Ryan
 * @since
 */
public class RBTree<T extends Comparable<T>> extends OrderBinaryTree<T> {

    @Override
    public void add(T t) {
        super.add(t);
        // 如果是空的，那么着色为黑色
        ((RBNode<T>)root).setColor(RBNode.BLACK);
    }

    @Override
    public void delete(T t) {
        // 红黑树的删除，是先调整再删除,这点与AVL树不同。
        final RBNode<T> node = (RBNode<T>) super.findNode(t);
        // 这个已经删除的节点是孤立的，没有任何意义
        if (root != null && node != null) {
            RBNode<T> replacement = (RBNode<T>) node.getReplacement();
            if (replacement == null) {
                replacement = node;
            }
            replacement.fixupAfterDeletion();
        }
        super.delete(t);
    }

    @Override
    protected OrderBinaryNode<T> createNode(T t) {
        return new RBNode<>(t);
    }

}
